package lyl.twopointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

 你返回所有和为 0 且不重复的三元组。

 注意：答案中不可以包含重复的三元组。

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/3sum
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ThreeSum {

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length <= 2){
            return result;
        }
        //先排序
        Arrays.sort(nums);
        //外部先定一个数，循环
        for (int i = 0; i < nums.length - 2 ; i++) {
            if(i > 0 && nums[i] == nums[i - 1]){//第一个数不允许重复
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] == 0){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    result.add(list);
                    //要求所有的各移动一个位置
                    left ++;
                    right --;
                    //如果与上一个位置相等，那就让指针再移动
                    while (left < right && nums[left] == nums[left - 1]){
                        left ++;
                    }
                    while (left < right && nums[right] == nums[right + 1]){
                        right --;
                    }
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    left ++;
                }else {
                    right --;
                }
            }
        }
        return result;
    }
}
